In typical computer systems a processor, dynamic random access memory (DRAM) controller, or similar apparatus executes commands. Execution usually involves performing some operation on data that is stored in a memory location and referenced using an address. For various reasons, for instance to increase the rate at which a processor can execute commands, commands may be scheduled by a computer system to be executed in a different order than the order in which they were issued. Out of order execution can improve system performance but also introduces the possibility of errors. For example, when a read command is scheduled to be executed out of order in advance of a write command that originally preceded it, the data read upon execution of the read command may not be the correct data. This is because the write command that was supposed to have placed the correct data at a particular address to be read by the read command has not been executed. This type of error is a read after write (RAW) error. Whenever a read command involving an address is scheduled ahead of a write command involving the same address a RAW hazard exists. In other words, it is possible that the RAW error may occur, but not certain.
Write after read (WAR) and write after write (WAW) hazards can also be created by scheduling commands for execution out of order (reordering). Read after read (RAR) hazards can also exist in a system in which read operations have side effects. Depending upon the type of task being accomplished by the command and the type of processing system, not all types of hazards may actually threaten the integrity of data. For example, for some tasks writes may never be reordered. Therefore, it is not always necessary to identify each type of hazard.
Prior methods of detecting reordering hazards typically require that a list of addresses be maintained for all outstanding commands and that an address associated with a new command be compared against the list. This method requires a great deal of hardware, the amount of hardware may be expressed as O(n*m) where n is the address width and m is the number of outstanding commands. If the number of outstanding commands is large, this method requires a prohibitively expensive amount of hardware. In fact, such systems are usually restricted to having no more than eight commands outstanding. The complexity and size of prior reordering hazard detection systems are further increased if commands may span multiple units of address. When a command is received it typically includes both an address and a length, where the length indicates a number of addressing units whose first addressing unit begins with the address included in the command. Addressing units may vary with particular systems or applications. For example, an addressing unit may refer to a word of 16 bits or a quad word of 64 bits. When a command indicates multiple addressing units, a hazard detection system must account for each address not explicitly stated. With prior methods this causes the amount of hardware to be increased to O(n*m*1), where 1 is the maximum command address span. If some false positive indications are acceptable, the hardware requirements may be reduced somewhat. In this situation hazards may be indicated where they do not actually exist. This is somewhat undesirable because when hazards are detected, system operation is slowed by the system taking steps to prevent commands from being reordered around the hazardous command. For some systems or applications, however, a number of false positive indications will not impact performance.
Even systems that can tolerate some false positive indications may still be unable to use prior hazard detection methods if large numbers of outstanding commands may exist. What is needed is a method for detecting reordering hazards that is not dependent on the number of outstanding commands and that requires only a small amount of additional hardware.
The present invention provides a method and apparatus for detecting reordering hazards for a target application that can tolerate some false positive indications. The present invention also includes methods for reducing the number of false positive indications. In one embodiment, the present invention includes two registers each large enough to accommodate an address. A first register stores an address associated with an initial write command. A second register accumulates information about addresses associated with subsequent write commands. The contents of the second register are used to mask an address associated with a read command before it is compared with the contents of the first register to determine if reordering hazards may occur.
In another embodiment, the present invention includes one register that can store at least 3 states in each position corresponding to each bit of an address. One state indicates that a bit of an address associated with a read command matches a corresponding bit of an address associated with an initial write command if the bit is a one. Another state indicates there is a match if the bit is a zero. Finally, a third, "force" state indicates that there is a match regardless of the state of the bit.
The present invention requires less hardware than traditional methods of hazard detection when more than two outstanding commands are considered. In addition, the present invention can detect reordering hazards more quickly and therefore allows for faster system operation. This is because the present invention only requires one address comparison whereas the prior method requires a comparison to be made for each address outstanding.